home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_400 / 425_01 / lzpipe / match.asm < prev    next >
Assembly Source File  |  1994-02-17  |  8KB  |  210 lines
  1. ; The following sorce code is derived from Info-Zip 'zip' 2.01
  2. ; distribution copyrighted by Mark Adler, Richard B. Wales,
  3. ; Jean-loup Gailly, Kai Uwe Rommel, Igor Mandrichenko and John Bush.
  4.  
  5. ; match.asm by Jean-loup Gailly.
  6.  
  7. ; match.asm, optimized version of longest_match() in deflate.c
  8. ; Must be assembled with masm -ml. To be used only with C compact model
  9. ; or large model. (For large model, assemble with -D__FAR__).
  10. ; This file is only optional. If you don't have masm or tasm, use the
  11. ; C version (add -DNO_ASM to CFLAGS in makefile.msc and remove match.obj
  12. ; from OBJI). If you have reduced WSIZE in zip.h, then change its value
  13. ; below.
  14. ;
  15. ; Turbo C 2.0 does not support static allocation of more than 64K bytes
  16. ; per file. So TC and BC++ users must use:
  17. ;   tasm -ml -DDYN_ALLOC match;
  18. ;
  19. ; To simplify the code, the option -DDYN_ALLOC is supported for OS/2 only
  20. ; if the arrays are guaranteed to have zero offset (allocated by halloc).
  21.  
  22.         ifdef   __FAR__
  23. arglist         equ    ss:[bp+6]
  24.  
  25. program         macro   progname
  26.                 public  progname
  27. progname        proc    far
  28.                 endm
  29.         else
  30. arglist         equ    ss:[bp+4]
  31.  
  32. program         macro   progname
  33.                 public  progname
  34. progname        proc    near
  35.                 endm
  36.         endif
  37.  
  38. ifndef DYN_ALLOC
  39.         extrn   _prev         : word
  40.         extrn   _window       : byte
  41.         prev    equ  _prev    ; offset part
  42.         window  equ  _window
  43. endif
  44.  
  45. _DATA   segment  word public 'DATA'
  46. ifdef DYN_ALLOC
  47.         extrn   _prev         : word
  48.         extrn   _window       : word
  49.         prev    equ 0         ; offset forced to zero
  50.         window  equ 0
  51.         window_seg equ _window[2]
  52.         window_off equ 0
  53.         prev_seg   equ _prev[2]
  54. else
  55.         window_seg dw  seg _window
  56.         window_off equ offset _window
  57.         prev_seg   dw  seg _prev     ; pointer to the prev array
  58. endif
  59.         extrn   _nice_match   : word
  60.         extrn   _match_start  : word
  61.         extrn   _prev_length  : word
  62.         extrn   _good_match   : word
  63.         extrn   _strstart     : word
  64.         extrn   _max_chain_length : word
  65. _DATA   ends
  66.  
  67. DGROUP  group _DATA
  68.  
  69. _TEXT   segment word public 'CODE'
  70.         assume  cs: _TEXT, ds: DGROUP
  71.  
  72.         MIN_MATCH     equ 3
  73.         MAX_MATCH     equ 258
  74.         WSIZE         equ 32768         ; keep in sync with zip.h !
  75.         MIN_LOOKAHEAD equ (MAX_MATCH+MIN_MATCH+1)
  76.         MAX_DIST      equ (WSIZE-MIN_LOOKAHEAD)
  77.  
  78. ; initialize or check the variables used in match.asm.
  79.  
  80.         program _match_init
  81. ifdef DYN_ALLOC
  82.         mov     ax,_prev[0]
  83.         or      ax,_window[0]   ; verify zero offset(s) - both in a turn
  84. else
  85.         xor     ax,ax
  86. endif
  87.         ret
  88. _match_init endp
  89.  
  90. ; Set match_start to the longest match starting at the given string and
  91. ; return its length. Matches shorter or equal to prev_length are discarded,
  92. ; in which case the result is equal to prev_length and match_start is
  93. ; garbage.
  94. ; IN assertions: cur_match is the head of the hash chain for the current
  95. ;   string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
  96.  
  97. ; int longest_match(cur_match)
  98.  
  99.         program _longest_match
  100.  
  101.         push    bp
  102.         mov     bp,sp
  103.         push    di
  104.         push    si
  105.         push    ds
  106.  
  107. ifdef __FAR__
  108.         cur_match    equ word ptr [bp+6] ; [bp+6] for large model
  109. else
  110.         cur_match    equ word ptr [bp+4] ; [bp+4] for compact model
  111. endif
  112.  
  113. ;       window       equ es:window (es:0 for DYN_ALLOC)
  114. ;       prev         equ ds:prev
  115. ;       match        equ es:si
  116. ;       scan         equ es:di
  117. ;       chain_length equ bp
  118. ;       best_len     equ bx
  119. ;       limit        equ dx
  120.  
  121.         mov     si,arglist[0]   ; = cur_match (use bp before it is destroyed)
  122.         mov     bp,_max_chain_length    ; chain_length = max_chain_length
  123.         mov     di,_strstart
  124.         mov     dx,di
  125.         sub     dx,MAX_DIST             ; limit = strstart-MAX_DIST
  126.         jae     limit_ok
  127.         sub     dx,dx                   ; limit = NIL
  128. limit_ok:
  129.         add     di,2+window_off         ; di = offset(window + strstart + 2)
  130.         mov     bx,_prev_length         ; best_len = prev_length
  131.         mov     es,window_seg
  132.         mov     ax,es:[bx+di-3]         ; ax = scan[best_len-1..best_len]
  133.         mov     cx,es:[di-2]            ; cx = scan[0..1]
  134.         cmp     bx,_good_match          ; do we have a good match already?
  135. ; Note: DS still points to static data (DGROUP)
  136.         mov     ds,prev_seg             ; (does not destroy the flags)
  137.         jb      do_scan                 ; good match?
  138.         shr     bp,1                    ; chain_length >>= 2
  139.         shr     bp,1
  140.         jmp     short do_scan
  141.  
  142.         even                            ; align destination of branch
  143. long_loop:
  144. ; at this point, es:di == scan+2, es:si == cur_match
  145.         mov     ax,es:[bx+di-3]         ; ax = scan[best_len-1..best_len]
  146.         mov     cx,es:[di-2]            ; cx = scan[0..1]
  147. ; Note: DS always points to static data here
  148.         mov     ds,prev_seg             ; reset ds to address the prev array
  149.         assume  ds: nothing
  150. short_loop:
  151. ; at this point, di == scan+2, si = cur_match,
  152. ; ax = scan[best_len-1..best_len] and cx = scan[0..1]
  153. if (WSIZE-32768)
  154.         and     si,WSIZE-1              ; not needed if WSIZE=32768
  155. endif
  156.         shl     si,1                    ; cur_match as word index
  157.         mov     si,prev[si]             ; cur_match = prev[cur_match]
  158.         cmp     si,dx                   ; cur_match <= limit ?
  159.         jbe     the_end
  160.         dec     bp                      ; --chain_length
  161.         jz      the_end
  162. do_scan:
  163.         cmp     ax,word ptr es:window[bx+si-1] ; check match at best_len-1
  164.         jne     short_loop
  165.         cmp     cx,word ptr es:window[si]      ; check min_match_length match
  166.         jne     short_loop
  167.  
  168.         lea     si,window[si+2]         ; si = match
  169.         mov     ax,di                   ; ax = scan+2
  170.         mov     cx,es
  171.         mov     ds,cx                   ; ds = es = window
  172.         mov     cx,(MAX_MATCH-2)/2      ; scan for at most MAX_MATCH bytes
  173.         repe    cmpsw                   ; loop until mismatch
  174.         je      maxmatch                ; match of length MAX_MATCH?
  175. mismatch:
  176.         mov     cl,[di-2]               ; mismatch on first or second byte?
  177.         sub     cl,[si-2]               ; cl = 0 if first bytes equal
  178.         xchg    ax,di                   ; di = scan+2, ax = end of scan
  179.         sub     ax,di                   ; ax = len
  180.         sub     si,ax                   ; si = cur_match + 2 + offset(window)
  181.         sub     si,2+window_off         ; si = cur_match
  182.         sub     cl,1                    ; set carry if cl == 0 (can't use DEC)
  183.         adc     ax,0                    ; ax = carry ? len+1 : len
  184.         pop     ds                      ; DS now points to static data
  185.         assume  ds: DGROUP
  186.         push    ds                      ; restore stack
  187.         cmp     ax,bx                   ; len > best_len ?
  188.         jle     long_loop
  189.         mov     _match_start,si         ; match_start = cur_match
  190.         mov     bx,ax                   ; bx = best_len = len
  191.         cmp     ax,_nice_match          ; len >= nice_match ?
  192.         jl      long_loop
  193. the_end:
  194.         pop     ds
  195.         pop     si
  196.         pop     di
  197.         pop     bp
  198.         mov     ax,bx                   ; result = ax = best_len
  199.         ret
  200.  
  201.         even
  202. maxmatch:                               ; come here if maximum match
  203.         cmpsb                           ; increment si and di
  204.         jmp     mismatch                ; force match_length = MAX_LENGTH
  205.  
  206. _longest_match  endp
  207.  
  208. _TEXT   ends
  209. end
  210.